package a07_二叉树;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * <p>
 * a04_二叉树的统一迭代法复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/1/8
 */
public class a04_二叉树的统一迭代法复习2 {
    //前序：中左右
    //      1
    //  2        3
    //4   5    6    7

    //是不是可以这样理解？
    //stack里面代表我们要处理的节点，
    //我们拿出要处理的节点进行处理后，然后将右放入，再放入左
    //下次我们就需要处理左节点了，处理完左节点后，我们将左节点的右放入，左放入
    //下次我们就需要处理左节点的右节点了
    //
    //
    //然后再理解统一迭代法
    //如果按照上面的不行，为啥呢，因为如果刚开始直接处理从stack取出来的root，那么中序和后序就不行
    //因此我们用Null标记了要处理的节点
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            if(stack.peek() != null){
                TreeNode popNode = stack.pop();
                //右
                if (popNode.right != null) {
                    stack.add(popNode.right);
                }
                if (popNode.left != null) {
                    stack.add(popNode.left);
                }
                stack.add(popNode);
                stack.add(null);
            }else {
                stack.pop();
                TreeNode popNode = stack.pop();
                result.add(popNode.val);
            }
        }
        return result;
    }
}
